<?php

namespace app\Service;

class ShuDu
{
    /**
     * @param $n 数字数量
     * @param $emptyN 空白格子
     * @param $grid 网格9x9=3,4x4=2 网格需要正方形
     * @return array
     */
    public function generateSudoku($n, $emptyN, $grid)
    {
        // 创建空白盒子
        $board = array_fill(0, $n, array_fill(0, $n, 0));

        $this->solveSudoku($board, $n, $grid);

        $board = $this->randomEmptyCells($board, $emptyN); // 设置空白格子

        return $board;
    }

    /**
     * 空白格子保证每行都有
     * @param $board
     * @param $numEmptyCells
     * @return array
     */
    protected function randomEmptyCells($board, $numEmptyCells)
    {
        $emptyCells = [];

        // 随机空白格子
        $num = count($board);
        $i = 0;
        while (count($emptyCells) < $numEmptyCells) {
            $row = rand(0, $num - 1);
            $col = rand(0, $num - 1);

            if ($i < $num) {
                $row = $i;
            }
            $i++;

            if ($board[$row][$col] == 0) {
                continue;
            }
            $emptyCells[] = [$row, $col];
            $board[$row][$col] = 0;
        }

        return $board;
    }

    protected function solveSudoku(&$board, $n, $grid)
    {
        if (empty($board)) {
            return false;
        }

        $emptyCell = $this->findEmptyCell($board, $n);

        if (!$emptyCell) {
            return true;
        }

        $row = $emptyCell[0];
        $col = $emptyCell[1];

        $mathArr = [];
        for ($i = 1; $i <= $n; $i++) {
            array_push($mathArr, $i);
        }

        shuffle($mathArr);

        foreach ($mathArr as $num) {
            if ($this->isValidMove($board, $row, $col, $num, $n, $grid)) {
                $board[$row][$col] = $num;

                if ($this->solveSudoku($board, $n, $grid)) {
                    return true;
                }

                $board[$row][$col] = 0;
            }
        }

        return false;
    }

    protected function findEmptyCell($board, $n)
    {
        for ($row = 0; $row < $n; $row++) {
            for ($col = 0; $col < $n; $col++) {
                if ($board[$row][$col] == 0) {
                    return [$row, $col];
                }
            }
        }

        return null;
    }

    /**
     * @param $board
     * @param $row
     * @param $col
     * @param $num
     * @param $n
     * @param $grid 网格
     * @return bool
     */
    protected function isValidMove($board, $row, $col, $num, $n, $grid)
    {
        // 验证网格如果积大于数量，则会引起死循环
        for ($i = 0; $i < $n; $i++) {
            if ($board[$row][$i] == $num || $board[$i][$col] == $num) {
                return false;
            }
        }

        $startRow = $row - $row % $grid;
        $startCol = $col - $col % $grid;

        if ($grid * $grid > $n) {
            return true;
        }
        for ($i = 0; $i < $grid; $i++) {
            for ($j = 0; $j < $grid; $j++) {
                if ($board[$i + $startRow][$j + $startCol] == $num) {
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * 解数独
     * @param $board
     * @param $n
     * @param $grid
     * @return array
     */
    public function isValidSudoku($board, $n, $grid)
    {
        $record = [];
        // 验证每一行
        for ($row = 0; $row < $n; $row++) {
            $rowSet = [];
            for ($col = 0; $col < $n; $col++) {
                if ($board[$row][$col] != 0) {
                    if (isset($rowSet[$board[$row][$col]])) {
//                        return [$row, $col];
                        $record[] = [$row, $col];
                    } else {
                        $rowSet[$board[$row][$col]] = true;
                    }
                }
            }
        }

        // 验证每一列
        for ($col = 0; $col < $n; $col++) {
            $colSet = [];
            for ($row = 0; $row < $n; $row++) {
                if ($board[$row][$col] != 0) {
                    if (isset($colSet[$board[$row][$col]])) {
//                        return [$row, $col];
                        $record[] = [$row, $col];
                    } else {
                        $colSet[$board[$row][$col]] = true;
                    }
                }
            }
        }
        if ($grid * $grid > $n || $grid == 0) {
            return $record;
        }
        // 验证每一个3x3的子方格
        for ($startRow = 0; $startRow < $n; $startRow += $grid) {
            for ($startCol = 0; $startCol < $n; $startCol += $grid) {
                $subgridSet = [];
                for ($row = $startRow; $row < $startRow + $grid; $row++) {
                    for ($col = $startCol; $col < $startCol + $grid; $col++) {
                        if ($board[$row][$col] != 0) {
                            if (isset($subgridSet[$board[$row][$col]])) {
//                                return [$row, $col];
                                $record[] = [$row, $col];
                            } else {
                                $subgridSet[$board[$row][$col]] = true;
                            }
                        }
                    }
                }
            }
        }

        return $record;
    }

}